Routing and Wavelength Assignment (RWA) is a well-known problem for fixed grid optical networks while Routing and Spectrum Assignment (RSA) is its equivalent term to the same problem for flexible grid optical networks or gridless optical networks. In fixed grid optical networks, wavelengths are spaced apart from each other according to a wavelength spectrum grid defined by International Telecommunication Union (ITU) in ITU-T G.694.1 (February 2012), “Spectral grids for WDM applications: DWDM frequency grid,” the contents of which are incorporated by reference. In flexible grid optical networks, which is also described in ITU Recommendation G.694.1 “Spectral grids for WDM applications: DWDM frequency grid” (February 2012), each signal can be allocated to spectrum with different widths optimized for the bandwidth requirements of the particular bit rate and modulation scheme of the individual channels. Note, flexible grid networks may still utilize a grid, albeit at a much finer granularity than grid networks (e.g., 6.25 GHz vs. 50 GHz). On the other hand, gridless networks have no such grid constraints. The ultimate objective of RWA or RSA is to find a wavelength or spectrum assignment on a route for a particular channel in the optical network, such assignment and routing being optimal in some manner. In the case of disjoint path computation, an objective is to find the shortest path of such routes with spectrum continuity.
In an optical network, path computation relates to finding a path given some criteria between two nodes in the optical network. A disjoint path computation includes determining two different paths which are separate (i.e., disjoint) for resiliency. Suurballe's algorithm is an algorithm for finding two disjoint paths in a non-negatively-weighted directed graph so that both paths connect the same pair of vertices and have minimum total length. The main idea of Suurballe's algorithm is to use Dijkstra's algorithm to find one path, to modify the weights of the graph edges, and then to run Dijkstra's algorithm a second time. The modification to the weights is similar to the weight modification in Johnson's algorithm and preserves the non-negativity of the weights while allowing the second instance of Dijkstra's algorithm to find the correct second path. However, for DWDM networks, there is an additional constraint of wavelength/spectral continuity for fixed grid or flexible grid networks, i.e., in DWDM networks, each link in a path must be on a same wavelength or portion of the spectrum. Due to this additional constraint, Suurballe's algorithm may not yield a feasible or optimal solution for spectrum continuity constraints.
To address this additional constraint of wavelength continuity, some existing solutions include. First, one approach is to apply spectrum continuity along with each Dijkstra iteration or after the two Dijkstra iterations in Suurballe's algorithm, but this can yield either infeasible solutions or no solution when one may exist. Another approach includes dividing the optical network into 128 networks for each wavelength in the 50 GHz grid and then evaluate for each combination to get the optimal solution which may include 128×128=4096 iterations of Suurballe's algorithm to get a optimal feasible solution. Conversely, for flexible grid networks, one approach includes dividing the network into 768 networks for each portion of the spectrum in 6.25 GHz increments and then evaluate for each combination to get the optimal solution which may be a 768×768=590K iterations of Suurballe's algorithm to get a optimal feasible solution. Thus, there are a very high number of iterations based on the resolution of flexible grid networks. Of course, these approaches are computationally complex, inefficient, slow, etc. with a high-performance penalty for a correct solution in some cases and no solution in gridless networks due to a continuous spectral range without any grid slots.
There is a need for efficient disjoint path computation systems and methods in optical networks which determine a pair of disjoint (separate) paths for providing resiliency in connections.